diff: trim endpoints of search more agressively.

When we find a long snake, we significantly reduce the worst-case
result (which is "no more snakes ever").  This allows us to trim the
end-points of the search-font.  If the endpoints have a best-case that
is worst than the worst-case when using the new snake, there is no point
pursuing them.
Previously we only trimmed the ends one step for each step forward.
This is unnecessarily cautious.  It is better to keep trimming until
the best-case at the end reaches the worst-case.

This improves one test case about 20%.

Signed-off-by: NeilBrown <neil@brown.name>

diff --git a/diff.c b/diff.c
index d95bef63d4b518a76f30e933e949ab10bf41354d..5270682463ec80985070b45e5d2bac8aa51ceed9 100644 (file)
--- a/diff.c
+++ b/diff.c
@@ -301,23 +301,29 @@ static int find_common(struct file *a, struct file *b,
                /* new location if we step up from klo to klo-1*/
                x = v[klo].x; y = x - (klo-1);
                cost = abs((ahi-x)-(bhi-y));
+               klo--;
                if (y <= bhi && cost <= worst) {
                        /* Looks acceptable - step up. */
-                       v[klo-1] = v[klo];
-                       klo--;
-               } else
-                       klo++;
+                       v[klo] = v[klo+1];
+               } else do {
+                               klo += 2;
+                               x = v[klo].x; y = x - (klo-1);
+                               cost = abs((ahi-x)-(bhi-y));
+                       } while (cost > worst);
 
                /* new location if we step to the right from khi to khi+1 */
                x = v[khi].x+1; y = x - (khi+1);
                cost = abs((ahi-x)-(bhi-y));
+               khi++;
                if (x <= ahi && cost <= worst) {
                        /* Looks acceptable - step to the right */
-                       v[khi+1] = v[khi];
-                       v[khi+1].x++;
-                       khi++;
-               } else
-                       khi--;
+                       v[khi] = v[khi-1];
+                       v[khi].x++;
+               } else do {
+                               khi -= 2;
+                               x = v[khi].x+1; y = x - (khi+1);
+                               cost = abs((ahi-x)-(bhi-y));
+                       } while (cost > worst);
        }
 }